//
// Created by wdq on 22-9-17.
//

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

struct Edge {
    int head;
    int tail;
    int weight;

    Edge() = default;

    Edge(int head, int tail, int weight) : head(head), tail(tail), weight(weight) {}


};


struct ALGraph {

    vector<Edge *> *edges;
    int edgeNum;
    int vexNum;
    const char *names;

    explicit ALGraph(const char *names) {
        this->edgeNum = 0;
        this->vexNum = int(strlen(names));
        this->names = names;
        this->edges = new vector<Edge *>();

    }

    void addArc(int head, int tail, int weight = 0) const {
        edges->emplace_back(new Edge(head, tail, weight));
    }

    void output() const {
        for (auto &i: *edges) {
            cout << names[i->head] << " -> " << names[i->tail] << endl;
        }
    }

    void output(Edge *edge) const {
        cout << names[edge->head] << " -> " << names[edge->tail] << " : " << edge->weight << endl;
    }
};

int findZeroDegree(vector<int> &degree) {
    for (int i = 0; i < degree.size(); i++) {
        if (degree[i] == 0) {
            return i;
        }

    }
    return -1;

}

bool topSort(ALGraph &G, vector<int> &res) {
    vector<int> degree(G.vexNum);
    stack<int> topStack;
    for (auto &i: *G.edges) {
        degree[i->tail]++;
    }
    int first = findZeroDegree(degree);
    if (first == -1) {
        return false;
    }
    topStack.push(first);
    while (!topStack.empty()) {
        int temp = topStack.top();
        res.emplace_back(temp);
        topStack.pop();
        for (auto &i: *G.edges) {
            if (i->head == temp) {
                if (--degree[i->tail] == 0) {
                    topStack.push(i->tail);
                }
            }

        }
    }
    return int(res.size()) == G.vexNum;
}


void criticalPath(ALGraph &G) {
    vector<int> top;
    if (!topSort(G, top)) {
        cout << "there is a loop way!" << endl;
        return;
    }

    vector<int> early(G.vexNum);
    for (int i = 0; i < G.vexNum; i++) {
        int temp = top[i];
        for (auto &edge: *G.edges) {
            if (edge->head == temp) {
                early[edge->tail] = max(early[edge->tail], early[edge->head] + edge->weight);
            }
        }
    }

    vector<int> late(G.vexNum);
    for (int i = 0; i < G.vexNum; i++) {
        late[i] = early.back();
    }
    for (int i = G.vexNum - 1; i >= 0; i--) {
        int temp = top[i];
        for (auto &edge: *G.edges) {
            if (edge->tail == temp) {
                late[edge->head] = min(late[edge->head], late[edge->tail] - edge->weight);
            }
        }
    }

    vector<int> edgeEarly;
    vector<int> edgeLate;
    for (auto &edge: *G.edges) {
        edgeEarly.emplace_back(early[edge->head]);
        edgeLate.emplace_back(late[edge->tail] - edge->weight);
    }
    for (auto &i: top) {
        cout << "v" << G.names[i] << " -> ";
    }
    cout << endl;
    int index = 0;
    for (auto &edge: *G.edges) {
        printf("<v%c , v%c> = ", G.names[edge->head], G.names[edge->tail]);
        printf("early: %d late: %d  ", edgeEarly[index], edgeLate[index]);
        printf("late - early: %d  ", edgeLate[index] - edgeEarly[index]);
        if (edgeLate[index] == edgeEarly[index]) {
            printf("Critical Path !");
        }
        printf("\n");
        index++;

    }


}

int main() {
    const char *p = "123456";
    ALGraph g(p);
    g.addArc(0, 1, 3);
    g.addArc(0, 2, 2);
    g.addArc(1, 3, 2);
    g.addArc(1, 4, 3);
    g.addArc(2, 3, 4);
    g.addArc(2, 5, 3);
    g.addArc(3, 5, 2);
    g.addArc(4, 5, 1);


//    g.output();

    criticalPath(g);


    return 0;
}